//program 2.5.0 dijkstra算法
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 1005; // 节点数，假设有1000个节点
const int INF = 0x3f3f3f3f; // 无穷大
int G[N][N], dist[N];   // G[][]为邻接矩阵，dist[i]表示源点到结点i的最短路径长度
int p[N];   // p[i]表示源点到结点i的最短路径上i的前驱结点
int n, m;   // n为结点数，m为边数
bool flag[N];   // 如果flag[i]等于true，说明结点i已经加入到S集合；否则i属于V-S集合

// u是源点，求源点到其他各个顶点的最短路径
void dijkstra(int u) {
    // 初始化操作。初始化dist数组，flag数组，p数组
    for(int i = 1; i <= n; i++) {
        dist[i] = G[u][i];
        flag[i] = false;
        if(dist[i] == INF)
            p[i] = -1;  // 不邻接
        else
            p[i] = u;   // 邻接
    }
    dist[u] = 0;
    flag[u] = true; // 把u加入S集合
    // 找最小结点，松弛，重复n-1次
    for(int i = 1; i < n; i++) {
        // step1: 找dist最小结点t
        int temp = INF, t = u;  // t记录结点的编号
        for(int j = 1; j <= n; j++) {   // 找V-S集合中dist[]最小值以及相应的结点编号
            if(!flag[j] && dist[j] < temp) {
                temp = dist[j];
                t = j;
            }
        }
        if(t == u) return;  // 找不到最小dist，则返回
        flag[t] = true; // 将t加入到集合S中
        // step2: 执行松弛操作。判断V-S集合中的结点是否可以借助t更新dist[]
        for(int j = 1; j <= n; j++) {
            if(!flag[j] && dist[j] > dist[t] + G[t][j]) {
                dist[j] = dist[t] + G[t][j];    // 更新最短距离
                p[j] = t;   // 记录前驱
            }
        }
    }
}

void findpath(int u) {
    if(u == -1)
        return;
    findpath(p[u]);
    cout << u << "\t";
}
int main() {
    int u,v,w,st;   //u,v表示结点，w表示u-v的距离，st表示源点
    int t;  // 测试用例数
    cout << "测试用例数:" << endl;
    cin >> t;
    while(t--) {
        cout << "输入结点数n和边数m：" <<endl;
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                G[i][j]=INF;    // 初始化邻接矩阵为无穷大
        // 输入一条边的两端点和权重
        cout << "输入一条边的两端点和权重 u v w:" << endl;
        while(m--) {
            cin >> u >> v >> w;
            G[u][v] = min(G[u][v], w);
        }
        // 输入源点
        cout << "输入源点st:" << endl;
        cin >> st;
        dijkstra(st);
        findpath(5);
    }
    return 0;
}

/**
输入结点数n和边数m：
5 8
输入一条边的两端点和权重 u v w:
1 2 2
1 3 5
2 3 2
2 4 6
3 4 7
3 5 1
4 3 2
4 5 4
输入源点st:
1
*/